package A1_回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC_51N皇后 {
    List<List<String>> result=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] cheersboard=new char[n][n];
        for(char[] c:cheersboard){
            Arrays.fill(c,'.');
        }
        backtracking(cheersboard,n,0);
        return result;
    }
    public void backtracking(char[][] cheersboard,int n,int row){
        if(row==n){
            result.add(list(cheersboard));
        }
        for(int i=0;i<n;i++){
            if(isvalid(row,i,cheersboard,n)){
                cheersboard[row][i]='Q';
                backtracking(cheersboard,n,row+1);
                cheersboard[row][i]='.';
            }
        }
        return;
    }
    //将二维数组转换为List
    public List<String> list(char[][] cheerboard){
        List<String> cheer=new ArrayList<>();
        for(char[] c:cheerboard){
//            cheer.add(Arrays.toString(c));
            cheer.add(String.copyValueOf(c));
        }
        return cheer;
    }
    public boolean isvalid(int row,int col,char[][] cheersboard,int n){
        //列
        for(int i=0;i<row;i++){
//        for(int i=0;i<row;++i){
            if(cheersboard[i][col]=='Q')
                return false;
        }//单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
        //45°
        for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
            if(cheersboard[i][j]=='Q')
                return false;
        }
        //135°
        for(int i=row-1,j=col+1;i>=0 && j<n ; i--,j++){
            if(cheersboard[i][j]=='Q')
                return false;
        }
        return true;
    }
    public static void main(String args[]) {
        char[] Str1 = {'h', 'e', 'l', 'l', 'o', ' ', 'r', 'u', 'n', 'o', 'o', 'b'};
        String Str2 = "";

        Str2 = Str2.copyValueOf( Str1 );//
        System.out.println("返回结果：" + Str2);
//        System.out.println(Str1);

        Str2 = Str2.copyValueOf( Str1, 2, 6 );
        System.out.println("返回结果：" + Str2);
        /**
         * Str2.copyValueOf( Str1 ); 使用整个输入字符数组来创建一个新的字符串对象。
         *
         * Str2.copyValueOf( Str1, 2, 6 ); 从输入字符数组的第 3 个字符（即偏移量为 2）开始，复制 6 个字符，并创建一个新的字符串对象
         *
         * */
    }
}
